package com.neobeai.algorithm.leetcode;

import java.util.Arrays;

/**
 * @author xp
 * @date 2024/12/9 16:07
 * @description
 */
public class Demo2 {

    /**
     * 合并两个有序数组
     * @param nums1 目标数组
     * @param m     原数组长度
     * @param nums2 待合并数组
     * @param n     待合并数组长度
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        // 最简单实现
        for (int i = 0; i < n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }

    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        // 使用双指针算法实现
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                nums1[p] = nums2[p2--];
                p--;
                continue;
            }
            if (p2 == -1) {
                nums1[p] = nums1[p1--];
                p--;
                continue;
            }
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1--];
            } else {
                nums1[p] = nums2[p2--];
            }
            p--;
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {2, 0};
        int m = 1;
        int[] nums2 = {1};
        int n = 1;
        merge2(nums1, m, nums2, n);
        System.out.println(Arrays.toString(nums1));
    }

}
